package com.seven.leetcode.problems;

import com.seven.leetcode.utils.ListNode;

import java.util.Arrays;

/**
 * 23. 合并K个升序链表
 * MergeSortedLinkedLists
 * https://leetcode-cn.com/problems/merge-k-sorted-lists/
 * 级别：Easy
 * <p>
 * 给你一个链表数组，每个链表都已经按升序排列。
 * 请你将所有链表合并到一个升序链表中，返回合并后的链表。
 * <p>
 * 示例 1：
 * 输入：lists = [[1,4,5],[1,3,4],[2,6]]
 * 输出：[1,1,2,3,4,4,5,6]
 * 解释：链表数组如下：
 * [
 * 1->4->5,
 * 1->3->4,
 * 2->6
 * ]
 * 将它们合并到一个有序链表中得到。
 * 1->1->2->3->4->4->5->6
 * <p>
 * 示例 2：
 * 输入：lists = []
 * 输出：[]
 * <p>
 * 示例 3：
 * 输入：lists = [[]]
 * 输出：[]
 *
 * @author : wenguang
 * @date : 2021/3/22 9:26
 */
public class MergeSortedLinkedLists {

    public static void main(String[] args) {
        int[] nums1 = new int[]{1, 2, 4};
        ListNode node1 = ListNode.fromArray(nums1);
        int[] nums2 = new int[]{1, 3, 4};
        ListNode node2 = ListNode.fromArray(nums2);
        ListNode[] nodes = new ListNode[]{node1, node2};
        System.out.println("in: \nnums1: " + Arrays.toString(nums1) + "\nnums2: " + Arrays.toString(nums2));
        ListNode result = mergeKLists(nodes);
        System.out.println("out: " + result);
    }

    public static ListNode mergeKLists(ListNode[] lists) {
        if (null == lists || lists.length == 0) {
            return null;
        }

        if (lists.length == 1) {
            return lists[0];
        }

        ListNode node = mergeTwoLists(lists[0], lists[1]);
        for (int i = 2; i < lists.length; i += 2) {
            ListNode temp = null;
            if (i + 1 < lists.length) {
                temp = lists[i + 1];
            }
            temp = mergeTwoLists(lists[i], temp);
            node = mergeTwoLists(node, temp);
        }

        return node;
    }

    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (null == l1) {
            return l2;
        }
        if (null == l2) {
            return l1;
        }

        ListNode node = new ListNode();
        ListNode head = node;

        while (null != l1 && null != l2) {
            if (l1.val <= l2.val) {
                node.next = l1;
                l1 = l1.next;
            } else {
                node.next = l2;
                l2 = l2.next;
            }

            node = node.next;
        }

        if (null != l1) {
            node.next = l1;
        }

        if (null != l2) {
            node.next = l2;
        }

        return head.next;
    }
}
